package leetcode.editor.cn;

//给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。 
//
// 注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。 
//
// 
//
// 示例 1： 
//
// 输入：a = "abcd", b = "cdabcdab"
//输出：3
//解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。
// 
//
// 示例 2： 
//
// 输入：a = "a", b = "aa"
//输出：2
// 
//
// 示例 3： 
//
// 输入：a = "a", b = "a"
//输出：1
// 
//
// 示例 4： 
//
// 输入：a = "abc", b = "wxyz"
//输出：-1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= a.length <= 10⁴ 
// 1 <= b.length <= 10⁴ 
// a 和 b 由小写英文字母组成 
// 
// Related Topics 字符串 字符串匹配 👍 256 👎 0

import java.util.Arrays;

//Java：重复叠加字符串匹配
public class RepeatedStringMatch_686 {
    public static void main(String[] args) {
        Solution solution = new RepeatedStringMatch_686().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int repeatedStringMatch(String a, String b) {
            int len1 = a.length(), len2 = b.length();
            char[] aa = a.toCharArray(), bb=b.toCharArray();
            int[] next = new int[len2];
            for (int i = 1,j=0; i < len2; i++) {
                while(j>0 && bb[i]!=bb[j])
                    j = next[j-1];
                if(bb[i]==bb[j]) j++;
                next[i] =j;
            }
            int max = len2/len1+2;
            for (int i = 0,j=0; i-j < len1*max; i++) {
                while(j>0 && aa[i%len1]!=bb[j]){
                    j=next[j-1];
                }
                if(aa[i%len1] == bb[j]) j++;
                if(j==len2) {
                    System.out.println(i+" "+j);
                    return (i+1)%len1>0?(i+1)/len1+1:(i+1)/len1;
                }
            }
            return -1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
